package com.itheima.leetcode.od.b.stack;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.stream.Collectors;

/**
 * (C卷,100分)- 堆栈中的剩余数字（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 向一个空栈中依次存入正整数，假设入栈元素 n(1<=n<=2^31-1)按顺序依次为 nx…n4、 n3、n2、 n1, 每当元素入栈时，如果 n1=n2+…+ny(y 的范围[2,x]， 1<=x<=1000)，则 n1~ny 全部元素出栈，重新入栈新元素 m(m=2*n1)。
 * <p>
 * 如：依次向栈存入 6、 1、 2、 3, 当存入 6、 1、 2 时，栈底至栈顶依次为[6、 1、 2]；当存入 3时， 3=2+1， 3、 2、 1 全部出栈，重新入栈元素 6(6=2*3)，此时栈中有元素 6；
 * <p>
 * 因为 6=6，所以两个 6 全部出栈，存入 12，最终栈中只剩一个元素 12。
 * <p>
 * 输入描述
 * <p>
 * 使用单个空格隔开的正整数的字符串，如”5 6 7 8″， 左边的数字先入栈，输入的正整数个数为 x， 1<=x<=1000。
 * <p>
 * 输出描述
 * <p>
 * 最终栈中存留的元素值，元素值使用空格隔开，如”8 7 6 5″， 栈顶数字在左边。 6 1 2 3
 * <p>
 * 用例
 * <p>
 * 输入	5 10 20 50 85 1
 * <p>
 * 输出	1 170
 * <p>
 * 说明	5+10+20+50=85， 输入 85 时， 5、 10、 20、 50、 85 全部出栈，入栈 170，最终依次出栈的数字为 1 和 170。
 * <p>
 * 输入	6 7 8 13 9
 * <p>
 * 输出	9 13 8 7 6
 * <p>
 * 说明	无
 * <p>
 * 输入	1 2 5 7 9 1 2 2
 * <p>
 * 输出	4 1 9 14 1
 * <p>
 * 说明	无
 * <p>
 * 题目解析
 * <p>
 * 本题较为简单的解题思路是：
 * <p>
 * 每当有元素num将要入栈前，都尝试num去依次减去栈顶到栈底方向的栈中元素（注意这只是遍历栈的过程，而不是弹栈过程）：
 * <p>
 * 如果有出现num == 0，则将遍历过栈元素全部弹栈，并压入num * 2。
 * <p>
 * 如果没有出现num == 0，则栈不做变动，只压栈num
 * <p>
 * 但是需要注意的是，对于情况1而言，我们需要注意题目描述中的这句话：
 * <p>
 * 每当元素入栈时，如果 n1=n2+…+ny(y 的范围[2,x]， 1<=x<=1000)，则 n1~ny 全部元素出栈，重新入栈新元素 m(m=2*n1)
 * <p>
 * 那么压栈 num * 2 是否也算新元素入栈呢？是否需要继续检查等价栈元素呢？
 * <p>
 * 我理解是需要的，即这个压栈num * 2 的过程是一个需要递归的过程。
 */
public class StackRemainingNumbers {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);
        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();*/

        String input = "5 10 20 50 85 1";
        int[] nums = Arrays.stream(input.split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        System.out.println(getResult(nums));
    }

    public static String getResult(int[] nums) {
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(nums[0]);

        for (int i = 1; i < nums.length; i++) {
            push(nums[i], stack);
        }

        return stack.stream()
                .map(String::valueOf)
                .collect(Collectors.joining(" "));
    }

    public static void push(int num, LinkedList<Integer> stack) {
        int sum = num;

        for (int i = stack.size() - 1; i >= 0; i--) {
            sum -= stack.get(i);

            if (sum == 0) {
                stack.subList(i, stack.size()).clear();
                push(num * 2, stack);
                return;
            } else if (sum < 0) {
                break;
            }
        }

        stack.push(num);
    }
}